Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Теорія графів.

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут прикладної математики та фундаментальних наук
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Група:
ПМ-21

Частина тексту файла

Міністерство освіти і науки України Національний університет “Львівська політехніка” Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Звіт про виконання лабораторної роботи №2 на тему: “Теорія графів ” Виконала : ст. гр. ПМ-21 Львів -2008 Теоретичні відомості: Якщо в графі G(х) через  позначити число дуг, що йдуть з вершини  у вершину , то матриця А= {} з n – стрічками та n –стовпцями називається матрицею суміжності вершин графа G(x). Heхай  і  відповідають матрицям суміжності та  ,тоді матрці + відповідають граф G(х)= + , який отримується об’єднанням дуг графів  та  на цій же множині вершини  . Матриці суміжності  відповідає мультиграф побудований таким чином : в вершину  з вершини  йде стільки дуг, скільки існує різних шляхів в  з  і складених із двох дуг, перша з яких належить графу , а друга . Ранг елемента − параметр, що дозволяє розподілити елементи графа в порядку їх вагомості Вагомість елемента тут визначається лише кількістю зв’язків з даного елемента з іншими. Характеризуючи значимість елемента рангом − структурним параметром, можна сказати, зо чим більший ранг елемента , тим більше він зв’язаний з іншими елементами графа. Правило Таррі. Щоб знайти шлях із вершини  в  в симетричному (зв’язному ) графі G(х) , досить дотримуватись правила : ніколи не проходити двічі по одному і тому ж коридору і тому ж напрямку; знаходячись у вершині  не вибирати того ребра ,яку привело у вершину  в перший раз, якщо є можливість іншого вибору. Транспортна сітка Т є сукупністю двох об’єктів: Зв’язного графа G= (X,) з властивостями : В графі відсутні петлі В графі G існує одна і лише одна вершина така, що множина =Ǿ. В графі G існує одна і лише одна вершина , така ,що множина  =Ǿ. Цілочисельною невід’ємною функцією С(u) , заданою на множині  дуг графа G. Вершина  називається входом сітки, вершина  - виходом. Значення функції С(u) на дузі u називається пропускною здатністю дуги. Нехай U- множина дуг, що заходять у вершину , U- множина дуг, що виходять з множини . Цілочисельна невід’ємна функція , задана на множині  дуг графа G, називається потоком ,якщо вона задовольняє такі умови: = (,)  С(u) Величина  - називаться величиною потоку  і позначається . Код програми: #include<iostream.h> #include<conio.h> class dijkstra { private: int graph[26][26]; int set[26],predecessor[26],mark[26],pathestimate[26]; int source,target; int num_of_vertices; public: int minimum(); void read(); void initialize(); void printpath(int); void algorithm(); void output(); }; void dijkstra::read() { num_of_vertices =26; int myGraph[26][26]={ {0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0}, {1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1}, {0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0}, {0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0}, {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0}, {0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0}, {0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0}, {0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0}, {1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0}, {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини